#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    /**
     * @brief Brute
     *  O(N^2)
     * @param g
     * @param s
     * @return int
     */
    int findContentChildren(vector<int> &g, vector<int> &s)
    {
        int count = 0;
        for (int i = 0; i < g.size(); i++)
        {
            for (int j = 0; j < s.size(); j++)
            {
                if (g[i] <= s[j] and g[i] != -1 and s[j] != -1)
                {
                    count++;
                    g[i] = -1;
                    s[j] = -1;
                    break;
                }
            }
        }
        return count;
    }

    /**
     * @brief
     * Two pointer and sorting
     * TC : O(N)
     * @param g
     * @param s
     * @return int
     */
    int findContentChildren_2(vector<int> &g, vector<int> &s)
    {
        int child = 0;
        int cookie = 0;
        int count = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        while (child < g.size() and cookie < s.size())
        {
            if (s[cookie] >= g[child])
            {
                count++;
                child++;
            }
            cookie++;
        }
        return count;
    }

    int findContentChildren_3(vector<int> &g, vector<int> &s)
    {
        sort(g.begin(), g.end(), less<int>());
        sort(s.begin(), s.end(), less<int>());
        int index = 0;
        for (int i = 0; i != s.size(); i++)
        {
            if (index < g.size() && g[index] <= s[i])
            {
                index++;
            }
        }
        return index;
    }

    int findContentChildren_4(vector<int> &g, vector<int> &s)
    {
        int count = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        for (int i = 0, j = 0; i < g.size() && j < s.size();)
        {
            if (s[j] >= g[i])
            {
                count++;
                j++;
                i++;
            }
            else
            {
                j++;
            }
        }
        return count;
    }
};
int main()
{

    system("pause");
    return 0;
}
